﻿// -----------------------------------------------------------------------
// <copyright file="Algorithm.cs" company="">
// TODO: Update copyright text.
// </copyright>
// -----------------------------------------------------------------------

namespace MenuGame2DXNA
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using Microsoft.Xna.Framework;

    /// <summary>
    /// TODO: Update summary.
    /// </summary>
    public class Algorithm
    {
        
        public List<Point> pSpread;
        public int npSpread;
        Point[] path;
        private Point[] unitStep;


        public Algorithm()
        {
            unitStep = new Point[4];
            //---Khoi tao luat di chuyen---
            unitStep[0].X = 0;
            unitStep[0].Y = 1;

            unitStep[1].X = 1;
            unitStep[1].Y = 0;

            unitStep[2].X = 0;
            unitStep[2].Y = -1;

            unitStep[3].X = -1;
            unitStep[3].Y = 0;

        }

        public void pFindSpread(Point pFrom, short[,] iPixel, int nRows, int nCols)
        {
            Point x = new Point();
            int[,] pathVisited;
            pSpread = new List<Point>();

            int tim = 1;
            int sum = 0;
            int lastsum = 0;
            pathVisited = new int[nRows, nCols];

            for (int i = 0; i < nRows; i++)
            {
                for (int j = 0; j < nCols; j++)
                {
                    pathVisited[i, j] = 0;
                }
            }
            bool isFounded = false;
            x = pFrom;

            Point pNext = new Point();

            pathVisited[x.X, x.Y] = 1;
            while (isFounded == false)
            {
                for (int i = 0; i < nRows; i++)
                {
                    for (int j = 0; j < nCols; j++)
                    {
                        if (pathVisited[i, j] == tim)
                        {
                            for (int iCount = 0; iCount <= 3; iCount++)
                            {
                                pNext.X = i + unitStep[iCount].X;
                                pNext.Y = j + unitStep[iCount].Y;

                                if ((pNext.X >= 0) && (pNext.X < nRows) && (pNext.Y >= 0) && (pNext.Y < nCols))
                                {
                                    if ((iPixel[pNext.X, pNext.Y] == 0) && (pathVisited[pNext.X, pNext.Y] == 0))
                                    {
                                        pathVisited[pNext.X, pNext.Y] = tim + 1;
                                        pSpread.Add(new Point(pNext.X, pNext.Y));
                                    }
                                }
                            }
                        }
                    }
                }

                if (isFounded == false)
                {
                    sum = 0;

                    for (int i = 0; i < nRows; i++)
                    {
                        for (int j = 0; j < nCols; j++)
                        {
                            sum += pathVisited[i, j];
                        }
                    }

                    if (sum == lastsum)
                    {
                        break;
                    }
                    else
                    {
                        lastsum = sum;
                    }
                }

                tim++;
            }
            npSpread = pSpread.Count;
        }


        public List<Point> findPath(Point pFrom, Point pTo, short[,] iPixel,int nRows, int nCols)
        {
            //Tìm kiếm sử dụng loang trên ma trận
            if(iPixel[pTo.X,pTo.Y] != 0 || pFrom.Equals(pTo))
                return new List<Point>();
            Point x = new Point();
            

            int tim = 1;
            int[,] pathVisited;
            pathVisited = new int[nRows, nCols];

            for (int i = 0; i < nRows; i++)
            {
                for (int j = 0; j < nCols; j++)
                {
                    pathVisited[i, j] = 0;
                }
            }

            x = pFrom;

            bool isFounded = false;
           
            Point pNext = new Point();
           
            int sum = 0;
            int lastsum = 0;

            pathVisited[x.X, x.Y] = 1;
           
            while (isFounded == false)
            {
                for (int i = 0; i < nRows; i++)
                {
                    for (int j = 0; j < nCols; j++)
                    {
                        if (pathVisited[i, j] == tim)
                        {
                            for (int iCount = 0; iCount <= 3; iCount++)
                            {
                                pNext.X = i + unitStep[iCount].X;
                                pNext.Y = j + unitStep[iCount].Y;

                                if ((pNext.X >= 0) && (pNext.X < nRows) && (pNext.Y >= 0) && (pNext.Y < nCols))
                                {
                                    if ((iPixel[pNext.X, pNext.Y] == 0) && (pathVisited[pNext.X, pNext.Y] == 0))
                                    {                                       
                                        pathVisited[pNext.X, pNext.Y] = tim + 1;                                        
                                    }
                                    if (pNext.Equals(pTo) )
                                    {
                                        isFounded = true;
                                    }
                                }
                            }
                        }
                    }
                }

                if (isFounded == false)
                {
                    sum = 0;
                   
                    for (int i = 0; i < nRows; i++)
                    {
                        for (int j = 0; j < nCols; j++)
                        {
                            sum += pathVisited[i, j];
                        }
                    }

                    if (sum == lastsum)
                    {                   
                        break; 
                    }
                    else
                    {
                        lastsum = sum;
                    }
                }

                tim ++;
            }
            

            if (isFounded)
            {
                //Nếu tìm được đường đi
               
                
                path = new Point[tim];


                Point curPos = new Point();
                curPos = pTo;
                path[tim-1] = pTo;
                while (pathVisited[curPos.X, curPos.Y] > 1)
                {
                    for (int iCount = 0; iCount <= 3; iCount++)
                    {
                        pNext.X = curPos.X + unitStep[iCount].X;
                        pNext.Y = curPos.Y + unitStep[iCount].Y;

                        if ((pNext.X >= 0) && (pNext.X < nRows) && (pNext.Y >= 0) && (pNext.Y < nCols))
                        {
                            if (pathVisited[pNext.X, pNext.Y] == tim - 1)
                            {
                                path[tim - 2] = pNext;
                                curPos = pNext;
                                tim = tim - 1;
                                break; // TODO: might not be correct. Was : Exit For
                            }
                        }
                    }
                }

            }
            else
            {
                path = null;
            }
            List<Point> ListPath = new List<Point>(); 
            if (path != null)
            {
                
                ListPath.AddRange(path);
                
                //ListPath.Add(ListPath[ListPath.Count - 2]);
                //ListPath.Add(ListPath[ListPath.Count - 2]);
                //ListPath.Add(ListPath[ListPath.Count - 4]);
                //ListPath.Add(ListPath[ListPath.Count - 5]);
                //ListPath.RemoveAt(0);
                
            }
            return ListPath;
        }
    
    }
}
